from typing import List


class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n_nums = len(nums2)
        n_stats = pow(2, n_nums)

        dp = [[float("inf")] * n_stats for _ in range(n_nums)]

        # 匹配第1个数
        for j in range(n_nums):
            # print(j, ":", nums2[j], "->", nums1[0] ^ nums2[j])
            dp[0][1 << j] = nums1[0] ^ nums2[j]

        # 匹配其他数
        for i in range(1, n_nums):
            for stat in range(n_stats):
                for j in range(n_nums):
                    if not (1 << j) & stat and dp[i - 1][stat] < float("inf"):
                        dp[i][stat | (1 << j)] = min(dp[i][stat | (1 << j)], dp[i - 1][stat] + (nums1[i] ^ nums2[j]))

        # for row in dp:
        #     print(row)

        return dp[-1][-1]


if __name__ == "__main__":
    print(Solution().minimumXORSum(nums1=[1, 2], nums2=[2, 3]))  # 2
    print(Solution().minimumXORSum(nums1=[1, 0, 3], nums2=[5, 3, 4]))  # 8
